NAND flash memory storage systems possess many attractive properties, such as low power consumption, fast access time and shock resistance. As a result, NAND flash memory has been widely adopted in mission-critical hard real-time systems such as aerospace systems, as well as soft real-time systems such as iPhones and tablets. A NAND flash memory storage system is different from other real-time systems in that the NAND flash memory system needs to provide both the worst case scenario system response time and average scenario system response time.
There are two approaches in conventional real time garbage collection for NAND flash storage systems. The first one is the task-driven free-space replenishment approach, and the second one is the partial garbage collection approach. The first approach aims to replenish several free pages to ensure that there will be enough free space to execute each real-time task. The second approach partitions one garbage collection process into several steps and distributes these steps to different time slots.
In the conventional approaches, due to unique constraints for NAND flash memory storage systems, the concept of garbage collection is different from that of the dynamic memory system. In particular, due to the constraint of “out of place update” in flash memory, the number of valid page copy operations in the victim block is unpredictable. Such uncertainties negatively impact the predictability of system response time, which renders the garbage collection management a major bottleneck for improving system performance.
In the conventional approaches discussed above, in order to provide a lower bound of the reclaimed space, the systems have to store the runtime information of each real-time task, which normally requires significant modification to existing file systems. In addition, the partial garbage collection mechanism needs to allocate certain extra physical blocks as a write buffer, and a queue needs to be maintained to record the garbage collection information. In the conventional partial garbage collection approach, the process of garbage collection is triggered at a relatively early stage. Such early triggering may further introduce a large amount of unnecessary garbage collection with a large number of extra valid page copies.
In order to solve the performance issue of partial garbage collection, a real-time flash translation layer (FTL) is proposed (“RFTL”). In RFTL, the partial garbage collection is distributed to different logical blocks, and each logical block is pre-allocated to three physical blocks (i.e., a primary block, a buffer block and a replacement block). RFTL can significantly reduce the number of unnecessary garbage collection processes. The first draw-back of RFTL is that the flash-space utilization of RFTL is relatively low. The second draw-back of RTFL is that the garbage collection process is triggered at an early stage due to RTFL's fixed physical block allocation. In spite of the fact that existing schemes satisfy real-time requirements, existing schemes make no attempt to provide a guaranteed average system response time. In addition, the space utilizations of existing schemes are very low because these schemes allocate a large amount of extra flash memory space to ensure real-time performance.